'''
钢条切割问题
    某公司出售钢条,出售介个与钢条长度之间的关系如下表

    长度i     1  2  3  4  5  6  7  8  9  10
    价格pi    1  5  8  9  10 17 17 20 24 30

    问题:现有一段长度为n的钢条和上面的价格表,求切割钢条方案,使得总收益最大

    长度为4的钢条的所有切割方案如下:
    4 : 9    1+3 : 1+8    2+2 : 5+5    1+1+2 : 1+1+5  1+1+1+1 : 1+1+1+1
    第三个方案最优

    思考:长度为n的钢条的不同切割方案有几种?

    钢条切割问题--递推式
        设长度为n的钢条切割后最优收益值为rn,可以得出递推式
        rn = max(pn,r1 + rn-1,r2 + rn-2,...,rn-1 + r1)
        第一个参数pn表示不切割的价值
        其他n-1个参数分别表示另外n-1种不同的切割方案,对方案i = 1,2,3,...,n-1
            将钢条切割为长度为i和n-i两段
            方案i的收益为切割两段的最优收益之和
        考察所有的i,选择其中收益最大的方案

    钢条切割问题--最优子结构
        可以将求解规模为n的原问题,划分为规模更小的子问题:完成一次切割后,可以将昌盛的两端钢条看成两个独立的钢条切割问题
        组合两个子问题的最优解,并在所有可能得两端切割方案中选取组合收益最大的,构成原问题的最优解
        钢条切割满足最优子结构:问题的最优解由相关子问题的最优解组合而成,这些子问题可以独立求解

        钢条切割问题还存在更简单的递归求解方法
            从钢条左边切割下长度为i的一端,只对右边剩下的一端继续进行切割,左边的不再切割
            递推式简化为:rn = max(pi + rn-i)
            不做切割的方案就可以描述为:左边一段长度为n,收益为pn,剩余一段长度为0,收益为r0 = 0

'''
import time

def cal_time(func):
    def wrapper(*args,**kwarge):
        t1 = time.time()
        result = func(*args,**kwarge)
        t2 = time.time()
        print('%s running time: %s secs.' % (func.__name__,t2 - t1))
        return result
    return wrapper

p = [0,1,5,8,9,10,17,17,20,24,30]

def cut_rod_recurision_1(p,n):
    if n == 0:
        return 0
    else:
        res = p[n]
        for i in range(1,n):
            res = max(res,cut_rod_recurision_1(p,i) + cut_rod_recurision_1(p,n-i))
        return res

@cal_time
def c1(p,n):
    return cut_rod_recurision_1(p,n)

def cut_rod_recurision_2(p,n):
    if n == 0:
        return 0
    else:
        res = 0
        for i in range(1,n+1):
            res = max(res,p[i] + cut_rod_recurision_2(p,n-i))
        return res

@cal_time
def c2(p,n):
    return cut_rod_recurision_2(p,n)

'''
动态规划算法
'''
@cal_time
def cut_rod_dp(p,n):
    r = [0]
    for i in range(1,n+1):
        res = 0
        for j in range(1,i+1):
            res = max(res ,p[j] + r[i-j])
        r.append(res)
    return r[n]

print(c1(p,10))
print(c2(p,10))
print(cut_rod_dp(p,10))

'''
这两个函数分别对应钢条切割问题中两种等价但表述不同的递推公式，核心都是通过递归求解 “长度为 n 的钢条的最大收益”，但分割思路略有差异。
钢条切割问题的背景
钢条切割问题的核心是：给定长度为n的钢条，以及价格表p[i]（p[i]表示长度为i的钢条的售价），通过将钢条切割成若干段（也可以不切割），使得总售价最大。
设r(n)为长度n的钢条的最大收益，则两个函数分别对应r(n)的两种递推定义。

    1. cut_rod_recurision_1 对应的递推公式
    该函数的思路是：将长度为n的钢条分割为任意两段（i和n-i），取两段最大收益之和的最大值，再与 “不切割”（直接卖长度n的钢条）的收益比较。
    递推公式可表示为：
    r(n)=max{p[n],max 1≤i≤n−1(r(i)+r(n−i))}
    基础情况：r(0) = 0（长度为 0 的钢条收益为 0）。
    解释：
    p[n]：不切割，直接以长度n出售的收益。
    r(i) + r(n-i)：将钢条切割为长度i和n-i两段，两段的最大收益之和（i的范围是 1 到n-1，确保两段都有长度）。
    最终r(n)取上述所有可能中的最大值。
    
    2. cut_rod_recurision_2 对应的递推公式
    该函数的思路是：固定第一段切割长度为i（i从 1 到n），剩下的长度n-i继续最优切割，取所有可能的p[i] + r(n-i)的最大值。
    递推公式可表示为：
    r(n)=max 1≤i≤n(p[i]+r(n−i))
    基础情况：r(0) = 0（同上）。
    解释：
    p[i]：切割下一段长度为i的钢条的收益。
    r(n-i)：剩下的长度n-i的钢条的最大收益（递归求解）。
    i的范围是 1 到n：当i = n时，n-i = 0，此时p[n] + r(0) = p[n]，等价于 “不切割” 的情况，因此无需单独考虑p[n]。

两个递推公式的关系
    两种递推公式在数学上是等价的，最终会得到相同的r(n)：
    第一种公式通过 “分割为两段” 涵盖了所有可能的切割方式（多段切割可视为多次两段切割的组合）。
    第二种公式通过 “固定第一段长度，剩余部分递归” 更直接地覆盖了所有切割方式（包括不切割，即i = n的情况）。
    实际应用中，第二种公式更常用（如动态规划的状态转移方程），因为它避免了重复计算（第一种公式中r(i)和r(n-i)可能重复递归）。

'''